#include <iostream>
#include <vector>
#include <functional>
using namespace std;

function<void(vector<int> &)> output = [](vector<int> &arr) -> void
{
    int length = arr.size();
    for (int i = 0; i < length; ++i)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
};

function<void(vector<int> &, int, int)> swapInVector = [](vector<int> &arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
};

void mergeSort(vector<int> &arr);
void mSort(vector<int> &arr, vector<int> &result, int left, int right);
void merge(vector<int> &arr, vector<int> &result, int left, int right);

void mergeSort(vector<int> &arr)
{
    vector<int> temp(arr.size());
    mSort(arr, temp, 0, arr.size() - 1);
}

void mSort(vector<int> &arr, vector<int> &result, int left, int right)
{
    if (left == right)
        return;
    int mid = (left + right) / 2;
    mSort(arr, result, left, mid);
    mSort(arr, result, mid + 1, right);
    merge(arr, result, left, right);
}

void merge(vector<int> &arr, vector<int> &result, int left, int right)
{
    int end_1 = (left + right) / 2;
    int start_2 = end_1 + 1;
    int index_1 = left;
    int index_2 = start_2;
    while (index_1 <= end_1 && index_2 <= right)
    {
        if (arr[index_1] <= arr[index_2])
        {
            result[index_1 + index_2 - start_2] = arr[index_1];
            index_1++;
        }

        else
        {
            result[index_1 + index_2 - start_2] = arr[index_2];
            index_2++;
        }
    }
    while (index_1 <= end_1)
    {
        result[index_1 + index_2 - start_2] = arr[index_1];
        index_1++;
    }
    while (index_2 <= right)
    {
        result[index_1 + index_2 - start_2] = arr[index_2];
        index_2++;
    }
    while (left <= right)
    {
        arr[left] = result[left];
        left++;
    }
}

int main()
{
    vector<int> arr = {6, 2, 1, 3, 5, 4, 9, 7, 5, 4, 11, 2, 9, 4, 7, 3, 8, 10};

    vector<int> temp(arr);
    output(temp);
    mergeSort(temp);
    output(temp);

    return 0;
}
